package SearchCategory.BinarySearch;

/**
 * @Author ：xu_xiaofeng.
 * @Date ：Created in 16:20 2021/2/5
 * @Description：
 */
public class BinarySearch {

    public int search(int[] array, int target) {

        // 该方式无法找到有多个重复值的情况
        // 如array = {0,1,1,1,2}。target=1.

        int index = -1;

        int low = 0, high = array.length - 1, mid;
        while (low <= high) {
//            mid = (low + high) / 2;//取偏左的中值
            mid = (low + high) >> 1;//取偏左的中值

            if (array[mid] == target) {
                index = mid;
                return index;
            } else if (array[mid] > target) {
                high = mid - 1;
            } else {
                // array[mid] < target
                low = mid + 1;
            }
        }

        return index;
    }

    int leftBoundSearch(int[] nums, int target) {
        int index = -1;

        int low = 0, high = nums.length, mid;

        while (low < high) {
//            mid = (low + high) / 2;// 取偏左的中值
            mid = (low + high) >> 1;//取偏左的中值

            if (nums[mid] >= target) {
                high = mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            }

        }
        if (nums[low] == target) {
            return low;
        }

        return index;
    }

    int rightBoundSearch(int[] nums, int target) {
        int index = -1;

        int low = 0, high = nums.length, mid;

        while (low < high) {
            mid = (low + high + 1) / 2;//取偏右的中值
            if (nums[mid] <= target) {
                low = mid;
            } else if (nums[mid] > target) {
                high = mid + 1;
            }
        }
        if (nums[high] == target) {
            return high;
        }

        return index;
    }
}
